from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        # @cache
        # def dfs(i):
        #     if i>=n:
        #         return 0
        #     # 对于第i个  选 or 不选
        #     return max(dfs(i+2)+nums[i],dfs(i+1))
        # return dfs(0)

        # dp max(dp[i+2])

        dp = [0] * (n + 2)
        for i in range(n):
            dp[i + 2] = max(dp[i] + nums[i], dp[i + 1])
        return dp[-1]